#include <dbg.h>
#include <gtest/gtest.h>
using namespace std;

#ifndef TRAVERSAL
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root != nullptr) {
            st.push(root);
        }

        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                dbg(TreeNode(*node));
                st.pop();
                if (node->right) {
                    dbg(TreeNode(*node->right));
                    st.push(node->right);
                }

                st.push(node);
                st.push(nullptr);

                if (node->left) {
                    dbg(TreeNode(*node->left));
                    st.push(node->left);
                }
            } else {
                st.pop();
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};
#else
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }

private:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) {
            return;
        }
        traversal(cur->left, vec);   // 左
        vec.push_back(cur->val);     // 中
        traversal(cur->right, vec);  // 右
    }
};
#endif

TEST(TEST_1_inorderTraversal_Test, inorderTraversal) {
    Solution s;

    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    vector<int> v = {1, 3, 2};
    EXPECT_EQ(v, s.inorderTraversal(root));
}

TEST(TEST_2_inorderTraversal_Test, inorderTraversal) {
    Solution s;

    TreeNode* root = new TreeNode(1);

    vector<int> v = {1};
    EXPECT_EQ(v, s.inorderTraversal(root));
}

TEST(TEST_3_inorderTraversal_Test, inorderTraversal) {
    Solution s;

    TreeNode* root = new TreeNode(1);

    vector<int> v = {1};
    EXPECT_EQ(v, s.inorderTraversal(root));
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}